/**
 * 广度优先
 * @param {number[][]} mat
 * @return {number[][]}
 */
export var updateMatrix = function (mat) {
  let rows = mat.length,
    cols = mat[0].length
  // 创建两个矩阵，一个用来记录每个位置的最小距离，一个用来记录每个位置是否被访问过
  let result = new Array(rows).fill(0).map(() => new Array(cols).fill(0))
  let visited = new Array(rows).fill(false).map(() => new Array(cols).fill(false))
  // 队列，用来记录待查询上下左右位置的当前位置。
  let queue = []
  // 初始化已访问的位置并加入队列（把0视作已访问的位置）
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (mat[i][j] === 0) {
        queue.push([i, j])
        visited[i][j] = true
      }
    }
  }
  // 计算旁边位置的与0距离（当前位置的距离+1），并加入队列
  function checkNear([i, j], [nearI, nearJ]) {
    if (nearI < 0 || nearI >= rows || nearJ < 0 || nearJ >= cols || visited[nearI][nearJ]) return
    result[nearI][nearJ] = result[i][j] + 1
    visited[nearI][nearJ] = true
    queue.push([nearI, nearJ])
  }

  while (queue.length) {
    let [i, j] = queue.shift()
    // 分别检查四个方向的位置
    checkNear([i, j], [i - 1, j])
    checkNear([i, j], [i + 1, j])
    checkNear([i, j], [i, j - 1])
    checkNear([i, j], [i, j + 1])
  }
  return result
}

/**
 * 动态规划
 * @param {number[][]} mat
 * @return {number[][]}
 */
export var updateMatrix2 = function (mat) {
  let m = mat.length,
    n = mat[0].length
  // 目标结果
  let dist = new Array(m).fill(0).map(() => new Array(n).fill(Number.MAX_SAFE_INTEGER))
  // 如果 (i, j) 的元素为 0，那么距离为 0
  for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) if (mat[i][j] == 0) dist[i][j] = 0

  // 只有 水平向右移动 和 竖直向下移动，递归的顺序是从左到右，从上到下
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      // 水平向左 是由同行左侧的元素递推算出来的
      if (i - 1 >= 0) dist[i][j] = Math.min(dist[i][j], dist[i - 1][j] + 1)
      // 垂直向下，是由同列上行的元素递推算出来的
      if (j - 1 >= 0) dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1)
    }
  }
  // 只有 水平向左移动 和 竖直向上移动，递归的顺序是从右到左，从下到上
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      // 水平向右 是由同行右侧的元素递推算出来的
      if (i + 1 < m) dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1)
      // 垂直向下，是由同列下行的元素递推算出来的
      if (j + 1 < n) dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1)
    }
  }
  return dist
}
